package leetcode

import kotlinetc.println


/**
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:

Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
 */


fun main(args: Array<String>) {


    //[0,1,2,0],
    //  [3,4,5,2],
    //  [1,3,1,5]

    //特殊情况
    val matrix = arrayOf(
            intArrayOf(1, 1),
            intArrayOf(0, 1)
    )
    setZeroes1(matrix)
    matrix.forEach {
        it.asList().println()
    }
}

//todo
/**
 * 由于 follow up 里面提议用 常数级别 的空间复杂度，但是设置成 0 后，会影响到后续 原来是 0 的判断，所以可以先 设置成一个其他数字，
 * 然后在遍历一次 设置成 0 ，但是这样无法找到一个合适的 marker ,所以还是得换一种思路
 * */
fun setZeroes(matrix: Array<IntArray>): Unit {

    val row = matrix.size
    val column = matrix[0].size

    val tag = Int.MIN_VALUE

    var i = 0
    var j = 0
    while (i < row) {
        while (j < column) {
            //row
            if (matrix[i][j] == 0) {
                matrix[i][j] = tag
                for (k in 0 until column) {
                    if (matrix[i][k] != 0 && matrix[i][k] != tag)
                        matrix[i][k] = tag
                }

                //column
                for (k in 0 until row) {
                    if (matrix[k][j] != 0 && matrix[k][j] != tag)
                        matrix[k][j] = tag
                }
            }
            j++
        }
        j = 0
        i++
    }


    i = 0
    j = 0
    while (i < row) {
        while (j < column) {
            if (matrix[i][j] == tag)
                matrix[i][j] = 0
            j++
        }
        j = 0
        i++
    }
}

//Classic
fun setZeroes1(matrix: Array<IntArray>) {

    val row = matrix.size
    val column = matrix[0].size

    var colset = false


    for (i in 0 until row) {
        if (matrix[i][0] == 0){
            colset = true
        }
        for (j in 1 until column) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    //从下到上的方式读取之前存储的 0 marker，如果从上到下，由于已经设置过 0 ,读取到后面的时候  //1 处的条件会一直成立
    for (i in row - 1 downTo 0) {
        for (j in column - 1 downTo 1) {  //第一行要特别处理

            if (matrix[i][0] == 0 || matrix[0][j] == 0) //1
                matrix[i][j] = 0

        }
        //针对   11
        //       01  特殊情况 此时第一行第一个和第一列第一个发生了重复，导致最后全部变成 0 ，必须额外记录一下

        if (colset)
            matrix[i][0] = 0
    }


}